W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Microchips produced by Byteland-Electronics are simple semiconductor panels with transistors located on top of them. The ends of some pairs of transistors are connected using special micro-wires. Micro-wires conduct electricity in one direction only and each of them is characterized by its impedance (impedance is a more advanced version of resistance). The quality of a microchip is measured as the number of different paths inside of the microchip with impedance equal exactly to .
By a path in the microchip we mean any way of getting from one transistor to another one (the second transistor can be the same as the first one), traveling through micro-wires in the direction of their electricity conduction. Each path consists of at least one micro-wire. A path can pass through any transistor and micro-wire an arbitrary number of times. Impedance of a path is defined as the product of the impedances of all micro-wires on that path.
Write a program which:
The first line of input contains four integers , , and (, , , ), separated by single spaces. represents the number of transistors in the microchip, - the number of micro-wires, - impedance of paths we are looking for and - the number by which division is performed. Each of the following lines contains three integers , and (, , ), separated by single spaces and representing a micro-wire with impedance , which conducts electricity from transistor to transistor . None of the ordered pairs appears more than once in a test case.
The first and only line of the standard output should contain one word NIESKONCZONOSC (i.e. infinity in Polish), if the number of paths with impedance is infinite, or the remainder of the division of the number of paths with impedance by in the opposite case.
For the input data:
4 6 6 1000 2 1 3 1 3 2 1 4 2 4 2 4 4 3 3 3 4 2
the correct result is:
5
and for the input data:
4 4 1 1000 2 1 1 4 2 1 3 4 1 1 3 1
the correct answer is:
NIESKONCZONOSC
In the first example, all paths with impedance are:
Task author: Jakub Radoszewski.